package red.book._2._4;

import edu.princeton.cs.algs4.StdRandom;
import red.book._2._1.Example;

@SuppressWarnings("rawtypes")
public class Median {
	public static Comparable select(Comparable[] a, int k) {
		StdRandom.shuffle(a);
		int lo = 0, hi = a.length - 1;
		while (hi > lo) {
			int j = partition(a, lo, hi);
			if (j == k)
				return a[k];
			else if (j > k)
				hi = j - 1;
			else if (j < k)
				lo = j + 1;
		}
		return a[k];
	}

	private static int partition(Comparable[] a, int lo, int hi) {
		int i = lo, j = hi + 1;
		Comparable v = a[lo];
		while(true) {
			while(Example.less(a[++i], v)) 
				if (i >= hi)
					break;
			while(Example.less(v, a[--j])) ;
			
			if(i >= j)
				break;
			
			Example.exch(a, i, j);
		}
		Example.exch(a, lo, j);
		return j;
	}
	
	public static void main(String[] args) {
		Comparable[] a = new Comparable[] {10, 5, 2, 3, 8};
		System.out.println(select(a, a.length/2));
	}

}
